1585D - Yet Another Sorting Problem - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int t, n;
int fwk[500005];
bool vis[500005], yes = 0;

void solve() {
    cin >> n; yes = 0;
    for(int i=1;i<=n;i++) vis[i] = 0;
    int i = 1;
    vector<pair<int, int>> vec(n);
    for(auto &e:vec) {
        cin >> e.first; e.second = i++;
        if(vis[e.first]) {yes = 1;}
        vis[e.first] = 1;
    }
    if(yes) {cout << "YES\n"; return ;}
    sort(vec.rbegin(), vec.rend());
    bool res=0;
    for(auto e:vec) {
        for(int cx=e.second;cx;cx-=cx&-cx)
            res ^= fwk[cx];
        for(int cx=e.second;cx<=n;cx+=cx&-cx)
            fwk[cx] ^= 1;
    }
    for(int i=1;i<=n;i++) fwk[i] = 0;
    cout << (res ? "NO\n" : "YES\n");
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin>>t;
    while(t--) solve();
}